package jm.algorithm.sort;

/**
 * @Description 二分搜索优化插入排序
 * @date 2022/5/3 9:33
 */
public class InsertionSortBinary<T extends Comparable<T>> extends Sort<T>  {

    @Override
    protected void sort() {
        for (int begin = 1; begin < arr.length; begin++) {
            // 备份待插入元素
            T v = arr[begin];
            // 获取插入目标索引
            int insertIndex = search(begin);
            // 往右挪动一位：[insertIndex,begin)
            // 两种挪动方式：
//            for (int i = begin - 1; i >= insertIndex ; i--) {
//                arr[i + 1] = arr[i];
//            }
            for (int i = begin; i > insertIndex ; i--) {
                arr[i] = arr[i - 1];
            }
            arr[insertIndex] = v;
        }
    }

    /**
     * 将source位置的元素插入到dest位置
     * @param source
     * @param dest
     */
    private void insert(int source, int dest){
        // 备份待插入元素
        T v = arr[dest];
        // 获取插入目标索引
        int insertIndex = search(source);
        for (int i = source; i > insertIndex ; i--) {
            arr[i] = arr[i - 1];
        }
        arr[insertIndex] = v;
    }

    /**
     * 利用二分搜索找到 index 位置元素的待插入位置
     * 传入索引包含了已经排好序的数组元素为：[0,index)；
     * @param index
     * @return
     */
    private int search(int index){
        T v = arr[index];
        int begin = 0;
        int end = index;
        while (begin < end){ // 当 begin 与 end 相等时退出循环
            int mid = (begin + end) >> 1;
            if (cmp(v,arr[mid]) < 0){
                end = mid;
            }else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}
